package com.jacky.排序;

public class 排序数组_912_快速排序 {
    // 快速排序的主要逻辑
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high); // 获取分区点
            quickSort(array, low, pivotIndex - 1); // 对分区点左侧的子数组进行递归排序
            quickSort(array, pivotIndex + 1, high); // 对分区点右侧的子数组进行递归排序
        }
    }

    // 分区函数，将数组分为两部分，并返回分区点的索引
    public static int partition(int[] array, int low, int high) {
        int pivot = array[low]; // 选取最左边的元素作为分区点
        int i = low;
        int j = high;
        while (i < j) {
            // 从右向左找到第一个小于分区点的元素
            while (i < j && array[j] >= pivot) {
                j--;
            }
            // 从左向右找到第一个大于分区点的元素
            while (i < j && array[i] <= pivot) {
                i++;
            }
            // 交换两个元素
            if (i < j) {
                swap(array, i, j);
            }
        }
        // 将分区点交换到正确的位置
        swap(array, low, i);
        return i; // 返回分区点的索引
    }

    // 交换数组中的两个元素
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 打印数组元素
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2, 7, 1, 6};
        System.out.println("Original array:");
        printArray(array);

        quickSort(array, 0, array.length - 1);

        System.out.println("Sorted array:");
        printArray(array);
    }
}
